package allwe.leetcode.LCR_078;


import java.util.concurrent.atomic.AtomicInteger;

/**
 * 美团算法
 *
 * 输入：lists = [[1,4,5],[1,3,4],[2,6,7,8,9]] 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ]
 * 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
 */
public class NO78_2 {

    public static void main(String[] args) {
        ListNode listNode_1 = buildListNode(1);
        ListNode listNode_1_1 = buildListNode(listNode_1, 4);
        buildListNode(listNode_1_1, 5);

        ListNode listNode_2 = buildListNode(1);
        ListNode listNode_2_1 = buildListNode(listNode_2, 3);
        buildListNode(listNode_2_1, 4);

        ListNode listNode_3 = buildListNode(2);
        buildListNode(listNode_3, 6);

        ListNode[] lists = new ListNode[3];
        lists[0] = listNode_1;
        lists[1] = listNode_2;
        lists[2] = listNode_3;


        ListNode listNode = mergeKLists(lists);

        while (true) {
            if (listNode == null) {
                break;
            }
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    /**
     * listNode做法
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        // 计算结果集大小 - 避免扩容操作
        AtomicInteger listSize = new AtomicInteger(0);
        for (ListNode listNode : lists) {
            getNextCount(listNode, listSize);
        }

        // 准备容器存放结果
        ListNode resultNode = null;

        // 死循环
        while (true) {
            if (listSize.get() == 0) {
                break;
            }
            // 记录最小值的Node
            ListNode minListNode = null;
            // 记录属于那个子链表
            Integer childListId = null;

            // 反复循环主数组
            for (int i = 0; i < lists.length; i++) {
                // 如果某个子链表被用光，就跳过
                if (lists[i] == null) {
                    continue;
                }
                // 初始化最小值
                if (null == minListNode) {
                    minListNode = lists[i];
                    childListId = i;
                    continue;
                }
                // 做比较
                if (lists[i].val < minListNode.val) {
                    minListNode = lists[i];
                    childListId = i;
                }
            }
            if (minListNode == null) {
                continue;
            }

            // 指针向后走一步
            if (lists[childListId] != null) {
                lists[childListId] = lists[childListId].next;
                listSize.decrementAndGet();
            }
            // 记录结果
            if (resultNode == null) {
                resultNode = buildListNode(minListNode.val);
            } else {
                if (null == resultNode.next) {
                    resultNode.next = buildListNode(resultNode, minListNode.val);
                } else {
                    ListNode a = resultNode.next;
                    while (true) {
                        if (a.next == null) {
                            a.next = buildListNode(a, minListNode.val);
                            break;
                        }
                        a = a.next;
                    }
                }

            }
        }
        return resultNode;
    }

    private static ListNode buildListNode(ListNode listNode, int val) {
        ListNode listNode1 = new ListNode();
        listNode1.val = val;

        listNode.next = listNode1;

        return listNode1;
    }

    private static ListNode buildListNode(int val) {
        ListNode listNode = new ListNode();
        listNode.val = val;

        return listNode;
    }

    private static void getNextCount(ListNode listNode, AtomicInteger listSize) {
        if (listNode == null) {
            return;
        }

        listSize.incrementAndGet();

        if (listNode.next != null) {
            getNextCount(listNode.next, listSize);
        }
    }
}
